import javax.swing.*;
import java.awt.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-02
 * Time: 17:34
 */
public class test {
    public static void main5(String[] args) {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.initArrV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShall(dist, parentPath);
        for (int i = 0; i < array.length; i++) {
            g.printPath(array[i], dist[i], parentPath[i]);
            System.out.println("*****************************************");
        }
    }

    public static void main4(String[] args) {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.initArrV(array);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
//负权回路实例
//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('y', 's', 1);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', -8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.BellmanFord('s', dist, parentPath);
        if (flg) {
            g.printPath('s', dist, parentPath);
        } else {
            System.out.println("存在负权回路");
        }
    }

    public static void main3(String[] args) {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.initArrV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);

        //搞不定负权值
        String str1 = "sytx";
        char[] array1 = str1.toCharArray();
        GraphByMatrix g1 = new GraphByMatrix(str1.length(), true);
        g1.initArrV(array1);
        g1.addEdge('s', 't', 10);
        g1.addEdge('s', 'y', 5);
        g1.addEdge('t', 'y', -7);
        g1.addEdge('y', 'x', 3);

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);
        g.printPath('s', dist, parentPath);
        System.out.println();
        int[] dist1 = new int[array.length];
        int[] parentPath1 = new int[array.length];
        g1.dijkstra('s', dist1, parentPath1);
        g1.printPath('s', dist1, parentPath1);
    }

    public static void main(String[] args) {
        char[] arrV = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
        GraphByMatrix g = new GraphByMatrix(arrV.length, false);
        g.initArrV(arrV);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(arrV.length, false);
        GraphByMatrix kminTree1 = new GraphByMatrix(arrV.length, false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
        System.out.println(g.prime(kminTree1, 'a'));
        kminTree1.printGraph();
    }

    public static void main1(String[] args) {
        System.out.println("=================================");
        GraphByMatrix graphByMatrix = new GraphByMatrix(4, false);
        char[] arrV = {'A', 'B', 'C', 'D'};
        graphByMatrix.initArrV(arrV);
        graphByMatrix.addEdge('A', 'B', 1);
        graphByMatrix.addEdge('A', 'D', 1);
        graphByMatrix.addEdge('B', 'A', 1);
        graphByMatrix.addEdge('B', 'C', 1);
        graphByMatrix.addEdge('C', 'B', 1);
        graphByMatrix.addEdge('C', 'D', 1);
        graphByMatrix.addEdge('D', 'A', 1);
        graphByMatrix.addEdge('D', 'C', 1);
        graphByMatrix.printGraph();
        System.out.println(graphByMatrix.getDevOfV('A'));
        graphByMatrix.bfs('C');
        graphByMatrix.dfs('B');
        graphByMatrix.dfsD('B');
        System.out.println("=================================");
        GraphByList graphByList = new GraphByList(4, true);
        graphByList.initArrV(arrV);
        graphByList.addEdge('A', 'B', 1);
        graphByList.addEdge('A', 'D', 1);
        graphByList.addEdge('B', 'A', 1);
        graphByList.addEdge('B', 'C', 1);
        graphByList.addEdge('C', 'B', 1);
        graphByList.addEdge('C', 'D', 1);
        graphByList.addEdge('D', 'A', 1);
        graphByList.addEdge('D', 'C', 1);
        graphByList.printGraph();
        System.out.println(graphByList.getDevOfV('A'));
        System.out.println();
    }
}
